package com.ds.bintree.LeetCode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: 储存父节点的方法
 * @date 2022/9/11 19:51
 */
public class Num236_LowestCommonAncestor {
    Map<Integer,TreeNode> map = new HashMap<>();
    Set<TreeNode> visited = new HashSet<>();

    /**
     * 先序遍历把所有结点的父节点（除了根节点）保存在hashmap中
     * @param root
     */
    public void PreorderTraversal(TreeNode root){
        if (root==null){
            return;
        }
        if (root.left!=null){
            map.put(root.left.val,root);
        }
        PreorderTraversal(root.left);
        if (root.right!=null){
            map.put(root.right.val,root);
        }
        PreorderTraversal(root.right);

    }

    /**
     * 从p开始往上找父节点，记录到set之中，再从q中往上找，如果set中contain了的话就是最近的祖先结点
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        PreorderTraversal(root);
        while(p!=null){
            visited.add(p);
            p=map.get(p.val);
        }
        while (q!=null){
            if (visited.contains(q)){
                return q;
            }
            q=map.get(q.val);
        }
        return null;
    }

//    public static void main(String[] args) {
//        Num236_LowestCommonAncestor test = new Num236_LowestCommonAncestor();
//        TreeNode temp=test.map.get(1);
//        System.out.println(temp);
//    }
}
